package 回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 组合总和II40.java
 * @createTime 2022年12月02日 16:04:00
 */
public class 组合总和II40 {
	List<List<Integer>> result = new ArrayList<>();

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Arrays.sort(candidates);
		backTrace(candidates, target, 0, 0);
		return result;
	}

	LinkedList list = new LinkedList();

	public void backTrace(int[] candidates, int target, int cur, int sum) {
		//结束条件,1. 值相等，2. 值大于目标值
		if (target == sum) {
			result.add(new ArrayList<>(list));
			return;
		}
		//因为不能重复所以从下一个位置开始
		for (int i = cur; i < candidates.length; i++) {
			if (sum + candidates[i] > target) {
				break;
			}
			//去重
			if (i > cur && candidates[i] == candidates[i - 1]) {
				continue;
			}
			list.add(candidates[i]);
			backTrace(candidates, target, i + 1, sum + candidates[i]);
			//取消选择
			list.removeLast();
		}
	}
}
